package leetcode.code0365;

import java.util.Stack;

public class Solution2 extends Solution365 {

	private int jug1;// 桶1容量
	private int jug2;// 桶2容量
	private int target;// 目标

	@Override
	public boolean canMeasureWater(int jug1Capacity, int jug2Capacity, int targetCapacity) {
		if (targetCapacity > jug1Capacity + jug2Capacity)// 不可能超出最大
			return false;
		if (targetCapacity == jug1Capacity + jug2Capacity)// 装满相等后续讨论不到
			return true;
		this.jug1 = jug1Capacity;//
		this.jug2 = jug2Capacity;//
		this.target = targetCapacity;
		Stack<int[]> s = new Stack<>();
		s.add(new int[] { 0, this.jug2 });
		while (!s.isEmpty()) {
			int[] cur = s.pop();
			int j1 = cur[0];
			int j2 = cur[1];
			if (j1 == 0 && j2 == 0)// 走到这里还没找到就是空了, 倒回初始状态了, 两桶都是空
				return false;
			if (j1 == this.target || j2 == this.target || j1 + j2 == this.target)
				return true;
			if (j1 == this.jug1) {// 桶1满了,则清空
				s.add(new int[] { 0, j2 });
			} else if (j2 == 0) {// 桶2空了,则填满
				s.add(new int[] { j1, this.jug2 });
			} else {// 桶2有水,桶1还没满,倒水
				int temp1 = this.jug1 - j1; // 桶1能接收得水
				int temp2 = j2; // 桶2能倒出的水
				if (temp1 < temp2) {// 桶1装满 桶2剩水
					s.add(new int[] { this.jug1, j2 - temp1 });
				} else {// 桶1装不满, 桶2倒空
					s.add(new int[] { j1 + j2, 0 });
				}
			}
		}
		return false;//
	}

	public boolean f(int j1, int j2) {// j1 里有多少水, j2里有多少水
		if (j1 == 0 && j2 == 0)// 走到这里还没找到就是空了, 倒回初始状态了, 两桶都是空
			return false;
		if (j1 == this.target || j2 == this.target || j1 + j2 == this.target)
			return true;
		// 规则
		boolean ans = false;
		if (j1 == this.jug1) {// 桶1满了,则清空
			ans = this.f(0, j2);
		} else if (j2 == 0) {// 桶2空了,则填满
			ans = this.f(j1, this.jug2);
		} else {// 桶2有水,桶1还没满,倒水
			int temp1 = this.jug1 - j1; // 桶1能接收得水
			int temp2 = j2; // 桶2能倒出的水
			if (temp1 < temp2) {// 桶1装满 桶2剩水
				ans = this.f(this.jug1, j2 - temp1);
			} else {// 桶1装不满, 桶2倒空
				ans = this.f(j1 + j2, 0);
			}
		}
		return ans;
	}

	public static void main(String[] args) {
		Solution2 so = new Solution2();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
	}

}
